CF1055F Tree and XOR

思路算法难度双高的一道trie树题目，代码是我看别人的打的，然后使用瞪眼法思考了半天才有了懂了些门路

题解：

先是对题意的一些简单转换：由于对于每一条xor链都可以看成是两个数（xor前缀）的结果，所以题目变成了对于长度为$n$的数列$val_i$（也就是xor前缀），求两两异或结果的第$k$小值

下面开始正文：

我们考虑以贪心的思路从高到低逐位推出ans每一位的值

构建trie树的同时，对于每一个$val_i$，我们计算出在当前答案进度下，与它配对所能得到0的方案数$cnt$，假如比当前剩余的$k$值小，就在$k$中减掉$cnt$，且当前位答案应为1，否则0

(上面的话可能很玄乎，毕竟是洛谷黑题CF2800pt呢，我争取再讲清楚点)

在某一层上，遍历时对于trie树上的两条链，我们发现会有三种情况，一种是小于答案的，我们会在减cnt时减掉并换一条链继续便利（因为另一条一定是更大的）；一种是大于答案的，我们不会去管（遍历）它；还有一种是（可能）等于答案的，也就是我们所要从上到下遍历的，注意到因为是两条链，因此对于每个$val_i$自己的链（代码中是$a[i]$），还要额外记一条能与它异或出答案的链（代码中是$b[i]$）

这样就是一个时空$O(62*N)$的算法

思路貌似有了呢，但代码难度还是十分高的

因为还有很重要的一点，由于朴素的trie内存会炸，所以我们要考虑滚存trie树（然后会使代码可读性极度下降，导致蒟蒻我一开始难以理解）

trie树滚存的大致思路是由于一层最多只有$n$个点，所以我们只保存改层$n$个点的两个子节点，并对于每个$val_i$记两个指针$a[i]$和$b[i]$（上面有提到），一个是自己的，一个是要与自己匹配的链的，每次开始处理新的一层，处理指针数组都要清空，在根据上一层的指针数组构建出这一层的trie树，为啥这不会导致节点混乱呢？大概是因为如果上一层两个$val_i$指向同一个节点的话，他们在新建的节点中的“指向”也不会发生改变

这样，空间复杂度就降到了$O(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e6+5;
int n,a[N],b[N],ch[N][2],sz[N];
/*a[]b[]上文有讲，ch[i][0/1]表示val[i]的左右节点编号，sz[]表示有多少val[i]经过这个节点*/
long long sum,ans,k,val[N];

signed main(){
    read(n);read(k);
    a[1]=b[1]=1; //1表示trie树的根节点
    for(int i=2;i<=n;i++){
        int x;long long y;
        read(x);read(y);
        val[i]=y^val[x]; //父节点编号保证小于自己，所以可以直接O(1)维护xor前缀
        a[i]=b[i]=1;
    }
    for(int i=61;i>=0;i--){
        int cnt=0;sum=0;
        for(int j=1;j<=n;j++) ch[j][0]=ch[j][1]=sz[j]=0; //清空上一层的
        for(int j=1;j<=n;j++){
            int &p=ch[a[j]][val[j]>>i&1]; //根据指针建新点
            if(!p) p=++cnt;
            sz[a[j]=p]++;
        }
        for(int j=1;j<=n;j++)
            sum+=sz[ch[b[j]][val[j]>>i&1]]; //统计在“可能相等”中会产生几对0
        int op=0; //op是当前位的答案
        if(sum<k) k-=sum,op=1,ans|=1ll<<i;
        for(int j=1;j<=n;j++)
            b[j]=ch[b[j]][val[j]>>i&1^op]; //看看b指针是否要换一条链
    }
    write(ans);
}
赏

fighter